\section{The two-hop walk: Discovery through pull}
\label{sec:2hop-10p}
In this section, we analyze the two-hop walk process on undirected
connected graphs, which is described by the following simple
iteration: In each round, for each node $u$, we add edge $(u,w)$ where
$w$ is drawn uniformly at random from $\nei{t}{1}{v}$, where $v$ is
drawn uniformly at random from $\nei{t}{1}{u}$; if $w$ equals $u$ or
an existing neighbor of $u$, then no new edge is added.  The two-hop
walk yields the following pull-based resource discovery protocol.  In
each round, each node $u$ contacts a random neighbor $v$, receives the
identity of a random neighbor $w$ of $v$, and sends its identity to
$w$.

While both the two-hop walk and the push-based triangulation process
perform linear work per round, they differ in how this work may be
distributed among the nodes.  In any given round, each new edge
$(u,v)$ added in the triangulation process can be associated with a
distinct ``mediator'' node $w$ such that $(u, w)$ and $(v, w)$ are
existing edges.  This cannot be always done for two-hop walks; in a
given round, multiple nodes may connect to new neighbors through a
single ``mediator'' node that is one-hop away from the nodes.

The main result of this section is that the two-hop walk process
transforms an arbitrary connected $n$-node graph to a complete graph
in $O(n \log^2 n)$ rounds with high probability.  We also establish an
$\Omega(n\log n)$ lower bound on the two-hop walk for almost all
$n$-node graphs.

As we did for the triangulation process, we establish the $O(n \log^2
n)$ upper bound by showing that the minimum degree of the graph
increases by a constant factor (or equals $n-1$) in $O(n \log n)$
rounds with high probability.  For analyzing the growth in the degree
of a node $u$, we consider two overlapping cases.  The first case is
when the two-hop neighborhood of $u$ is not too large, i.e.,
$|\nei{t}{2}{u}| < \md{0}/3$, and the second is when the two-hop
neighborhood of $u$ is not too small, i.e., $|\nei{t}{2}{u}| \ge
\md{0}/4$.

% The proofs of
%the following three claims that establish the upper bound are deferred
%to Appendix~\ref{app:2hop}.

\begin{lemma}[{\bf When the two-hop neighborhood is not too large}]
\label{lem:mingrowth-1-10p}
There exists $T=O(n\log n)$ such that with probability at least
$1-1/n^2$, we have $\abs{\nei{T}{2}{u}} \ge \md{0}/3$ or $\dg{T}{u}
\ge \min\cub{2\md{0},n-1}$.
\end{lemma}
\begin{proof}
In the following, we use integers $T$, $T_1$, $T_2$, and $T_3$, each
bounded by $O(n \log n)$, whose precise values will be set at various
points of the proof to satisfy desired conditions.  We assume that
$\dg{t}{u} < 2 \md{0}$ for all $t < T$; otherwise, the desired claim
of the lemma holds.

By the definition of $\md{0}$, $\dg{0}{w} \ge \md{0}$ for all
$w$ in $\nei{0}{1}{u}$.  Let $X$ be the first round at which
$|\nei{X}{2}{u}| \ge \md{0}/3$.  We consider two cases.  If $X$ is at
most $c n \log n$ for a constant $c$ to be specified later, then the
claim of the lemma holds.  In the remainder of this proof we consider
the case where $X$ is greater than $cn \log n$; thus, for $0 \le t \le
cn\log n$, $|\nei{t}{2}{u}| <\md{0}/3$.

Fix a node $v$ in $\nei{0}{2}{u}$.  In the following, we first show
that in $O(n\log n)$ rounds, $v$ is strongly tied to the neighbors of
$u$ with probability at least $1-1/n^3$.  Let $T_1$ denote the first
round at which $v$ is strongly tied to $\nei{T_1}{1}{u}$, i.e., when
$|\nei{T_1}{1}{v} \cap \nei{T_1}{1}{u}| \ge \md{0}/2$.  We know that
$v$ has at least one neighbor, say $w_1$, in $\nei{0}{1}{u}$.  Since
$\dg{0}{w_1} \ge \md{0}$ and $|\nei{0}{2}{u}| <\md{0}/3$, $w_1$ has at
least $2\md{0}/3$ edges to nodes in $\nei{0}{1}{u}$.  Consider any $t
< T_1$.  By our definition of $T_1$, $v$ is weakly tied to
$\nei{t}{1}{u}$, and hence also to $\nei{0}{1}{u}$ since the latter is
a subset of the former.  Therefore, at time $t$, $w_1$ has at least
$2\md{0}/3 - \md{0}/2 = \md{0}/6$ neighbors in $\nei{0}{1}{u}$ which
do not have an edge to $v$ at time $t$.  Since $\dg{t}{w_1} \le
5\md{0}/2$, we obtain
\begin{eqnarray}
\prob{v\mbox{ connects to a node in }\nei{0}{1}{u} \setminus \nei{t}{1}{u} \mbox{ through
  }w_1\mbox{ in round $t$}} \ge \frac{1}{n}\cdot\frac{\md{0}}{6}\cdot \frac{2}{5\md{0}} = \frac{1}{15n} \label{eqn:2.hop.connect}
\end{eqnarray}
Let $e_1$ denote the event $\cub{v\mbox{ connects to a new node in
  }\nei{0}{1}{u}}$, and $X_1$ be the number of rounds for $e_1$ to
occur.  When $e_1$ occurs, let $w_2$ denote a witness for $e_1$; i.e.,
$w_2$ is a node in $\nei{0}{1}{u}$ to which $v$ connects in round
$X_1$.  We note that $w_1,w_2\in \nei{0}{1}{u}\subseteq
\nei{X_1}{1}{u}$. If $v$ is weakly tied to $\nei{X_1}{1}{u}$, both
$w_1$ and $w_2$ have at least $\md{0}/6$ neighbors in
$\nei{X_1}{1}{u}$ that do not have an edge to $v$ yet. Let $e_2$
denote the event $\cub{v\mbox{ connects to a new node in
  }\nei{X_1}{1}{u}}$, and $X_2$ be the number of rounds for $e_2$ to
occur.  In the two-hop walk, the event that a two-hop walk from $v$
connects to a node through $w_1$ is mutually exclusive from the event
that a two-hop walk from $v$ connects to a node through $w_2$.  Since
the lower bound of Equation~\ref{eqn:2.hop.connect} applies to both
$w_1$ and $w_2$, we obtain that $\prob{e_2} \ge 2/(15n)$.  Similarly,
we define $e_3,X_3,\dots, e_{\md{0}/2},X_{\md{0}/2}$ and obtain
$\prob{e_i} \ge i/(15n)$.  We now apply
Lemma~\ref{lem:couponcorollary-10p} to obtain that $X_1+X_2+\ldots
X_{\md{0}/2}$ is at most $75n\ln n$ with probability at least $1 -
1/n^4$.  Thus, with probability at least $1 - 1/n^4$, $T_1 \le 75n \ln
n$.  This is true for each $v$ in $\nei{0}{2}{u}$.  Thus, with
probability at least $1 - 1/n^3$, every node in $\nei{0}{2}{u}$ is
strongly tied to $\nei{0}{1}{u}$ in at most $75 n \ln n$ rounds.  Once
this event happens, we obtain that for any $v \in \nei{0}{2}{u}$,
\[\prob{u\mbox{ connects to }v\mbox{ in a single round}} \ge \frac{\md{0}/2}{2\md{0}}\cdot\frac{1}{n} = \frac{1}{4n}.\]
which implies that with probability at least $1 - 1/n^3$, $u$ has an
edge to every node in $\nei{0}{2}{u}$ in another $T_2 \le 12 n \ln
n$ rounds.

Let $T_3$ equal $T_1 + T_2$; we set $c$ to be a constant such that
that $X > 3T_3$.  We thus have $\nei{0}{2}{u}\subseteq
\nei{T_3}{1}{u}$, $\nei{0}{3}{u}\subseteq \nei{T_3}{1}{u}\cup
\nei{T_3}{2}{u}$, and $\nei{0}{4}{u}\subseteq \nei{T_3}{1}{u}\cup
\nei{T_3}{2}{u}\cup \nei{T_3}{3}{u}$. We now repeat the above analysis
again twice and obtain that at time $T = 3T_3$, $\nei{0}{2}{u}\cup
\nei{0}{3}{u}\cup \nei{0}{4}{u}\subseteq \nei{T}{1}{u}$ with
probability at least $1-\abs{\nei{0}{2}{u}\cup \nei{0}{3}{u}\cup
  \nei{0}{4}{u}}/n^3 \ge 1-1/n^2$.  By Lemma
\ref{lem:moreneighbor-10p}, we have $\abs{\nei{T}{1}{u}}\ge
\min\cub{2\md{0}, n-1}$, thus completing the proof of the lemma.
\end{proof}


\begin{lemma}[{\bf When the two-hop neighborhood is not too small}]
\label{lem:mingrowth-2-10p}
There exists $T=O(n\log n)$ such that with probability at least
$1-1/n^2$ we have $\abs{\nei{T}{2}{u}} < \md{0}/4$ or
$\dg{T}{u} \ge \min\cub{(1+1/8)\md{0},n-1}$.
\end{lemma}
\begin{proof}
Let $X$ be the first round at which $\nei{X}{2}{u} < \md{0}/4$. We
consider two cases. If $X$ is at most $cn\log n$ for a constant $c$ to
be specified later, then the claim of the lemma holds. In the
remainder of this proof we consider the case where $X$ is greater than
$cn\log n$; thus, for $0\le t\le cn\log n$, $\abs{\nei{t}{2}{u}} \ge
  \md{0}/4$. If $v\in \nei{0}{2}{u}$ is strongly tied to $\nei{0}{1}{u}$,
then
\[\prob{u\mbox{ connects to }v\mbox{ in a single round}} \ge
\frac{\dgi{t}{v}{\nei{0}{1}{u}}}{\abs{\nei{t}{1}{u}}}\cdot
\frac{1}{n}\ge \frac{\md{0}/4}{(1+1/8)\md{0}}\cdot \frac{1}{n} =
\frac{2}{9n}.\] Thus, in $T = 13.5n\ln n$ rounds, $u$ will add an edge
to $v$ with probability at least $1-1/n^3$.  If there are at least
$\md{0}/8$ nodes in $\nei{0}{2}{u}$ that are strongly tied to
$\nei{0}{1}{u}$, then $u$ will add edges to all these nodes in $T$
rounds with probability at least $1-1/n^2$.

In the remainder of this proof, we focus on the case where the number
of nodes in $\nei{0}{2}{u}$ that are strongly tied to
$\nei{0}{1}{u}$ at the start of round $0$ is less than $\md{0}/8$.  In
this case, because $\abs{\nei{t}{2}{u}}\ge \md{0}/4$, more than
$\md{0}/8$ nodes in $\nei{0}{2}{u}$ are weakly tied to
$\nei{0}{1}{u}$, and, thus, have at least $3\md{0}/4$ edges to
nodes in $\nei{0}{2}{u}\cup \nei{0}{3}{u}$.

In the following we show $u$ will connect to $\md{0}/8$ nodes in
$O(n\log n)$ rounds with probability at least $1-1/n^2$.  For any
round $t$, let $W_t$ denote the set of nodes in $\nei{t}{2}{u}$ that
are weakly tied to $\nei{t}{1}{u}$.  We refer to a length-2 path from
$u$ to a node two hops away as an {\em out-path}.  Let $P_0$ denote
the set of out-paths to $W_0$.  Since we have at least $\md{0}/8$
nodes in $\nei{0}{2}{u}$ that are weakly tied to $\nei{0}{1}{u}$,
$\abs{P_0}$ is at least $\md{0} /8$ at time $t=0$. Define $e_1=\cub{u
  \mbox{ connects to a new node in }\nei{0}{2}{u} \mbox{ through an out-path
  in } P_0}$, and $X_1$ to be the number of rounds for $e_1$ to occur.
  When $0\le t\le X_1$, for each $w_i\in \nei{t}{1}{u}$, let $p_i$ be
  the number of edges from $w_i$ to nodes in $\nei{0}{2}{u}$ that are
  weakly tied to $\nei{0}{1}{u}$.
\begin{eqnarray*}
\prob{e_1} 
&\ge& \sum_i \frac{1}{\dg{t}{u}} \cdot \frac{p_i}{\dg{t}{w_i}} 
\;\;\;\ge\;\;\; \sum_i \frac{1}{\dg{t}{u}} \cdot \frac{p_i}{n-1} 
\;\;\;\ge\;\;\; \frac{\sum_i p_i}{(1+1/8)\md{0}(n-1)} \\
&=& \frac{\abs{S}}{(1+1/8)\md{0}(n-1)} 
\;\;\;\ge\;\;\; \frac{\md{0}/8}{(1+1/8)\md{0}(n-1)} 
\;\;\;\ge\;\;\; \frac{1}{9n}.
\end{eqnarray*}
After $X_1$ rounds, $u$ will pick an out-path in $P_0$.  Let the node
$u$ connects to through this out-path be $v_1$.  Define $P_1$ to be
the set of out-paths from $u$ to $W_{X_1}$.  In general, for $i > 1$,
we define $e_i$, $P_i$, $X_i$, $v_i$ and $Y_i$ as follows.  Let $e_i$
denote the event $\cub{u \mbox{ connects to a new node in }
  \nei{0}{2}{u} \mbox{ through an out-path in } P_{i-1}}$.  Let $X_i$
be the number of rounds after event $e_{i}$ that it takes for $u$ to
pick an out-path in $P_{i-1}$, $v_i$ to be a node to which $u$
connects through this out-path, and $P_i$ to be the set of out paths
from $u$ to $W_{Y_i}$, where $Y_i = \sum_{j \le i} X_j$.

We show by induction that $\Pr[e_i] \ge i/(9n)$ and $|P_i \setminus
P_{i-1}| \ge \md{0}/8$.  We have established the induction base $i =
1$ above.  We now establish the induction step.  Since $v_i\in
\nei{0}{2}{u}$ is added to $\nei{Y_i}{1}{u}$, those out-paths in
$P_{i-1}$ consisting of edges from $v_i$ to nodes in $\nei{0}{1}{u}$
are not in $P_i$. The number of out-paths we lose because of this is
at most $\md{0}/4$.  But $v_i$ also has at least $3\md{0}/4$ edges to
$\nei{0}{2}{u}\cup \nei{0}{3}{u}$. The end points of these edges are
in $\nei{Y_i}{1}{u}\cup \nei{Y_i}{2}{u}$. If more than $\md{0}/8$ of
them are in $\nei{Y_i}{1}{u}$, then $\dg{Y_i}{u}\ge
(1+1/8)\md{0}$. Now let's consider the case that less than $\md{0}/8$
such end points are in $\nei{Y_i}{1}{u}$. This means the number of
edges from $v_i$ to $\nei{Y_i}{2}{u}$ is at least $3\md{0}/4 -
\md{0}/4 - \md{0}/8 = 3\md{0}/8$.  Among the end points of these
edges, if more than $\md{0}/8$ of them are strongly tied to
$\nei{Y_i}{1}{u}$, then the degree of $u$ will become at least
$(1+1/8)\md{0}$ in $O(n \log n)$ rounds with probability $1-1/n^2$ by
our earlier argument. If not, we know that more than $\md{0}/4$ newly
added edges are pointing to nodes that are weakly tied to
$\nei{Y_i}{1}{u}$.  Thus, $\abs{P_i \setminus P_{i-1}}$ is at least
$\md{0}/4$, and we obtain from the induction hypothesis $\abs{P_i} \ge
(i-1) \md{0}/8 + \md{0}/8 = i \md{0}/8$.  Thus, during round $t$,
$Y_{i-1}\le t\le Y_i$, $\prob{e_i}$ is at least $\frac{i}{9n}$.

\junk{
We now place a lower
bound on $|P_1 \setminus P_0|$.  Since $v_1\in \nei{0}{2}{u}$ is added
to $\nei{X_1}{1}{u}$, those out-paths in $P_0$ consisting of edges
from $v_1$ to nodes in $\nei{0}{1}{u}$ are not in $P_1$. The number of
out-paths we lose because of this is at most $\md{0}/4$.  But $v_1$
also has at least $3\md{0}/4$ edges to $\nei{0}{2}{u}\cup
\nei{0}{3}{u}$. The end points of these edges are in
$\nei{X_1}{1}{u}\cup \nei{X_1}{2}{u}$. If more than $\md{0}/8$ of them
are in $\nei{X_1}{1}{u}$, then $\dg{X_1}{u}\ge (1+1/8)\md{0}$. Now
let's consider the case that less than $\md{0}/8$ such end points are
in $\nei{X_1}{1}{u}$. This means the number of edges from $v_1$ to
$\nei{X_1}{2}{u}$ is at least $3\md{0}/4 - \md{0}/4 - \md{0}/8 =
3\md{0}/8$.  Among the end points of these edges, if more than
$\md{0}/8$ of them are strongly tied to $\nei{X_1}{1}{u}$, then the
degree of $u$ will become at least $(1+1/8)\md{0}$ in $O(n \log n)$
rounds with probability $1-1/n^2$ by our earlier argument. If not, we
know that more than $\md{0}/4$ newly added edges are pointing to nodes
that are weakly tied to $\nei{X_1}{1}{u}$.  Thus, $\abs{P_1 \setminus
  P_0}$ is at least $\md{0}/4$, and $\abs{P_1} \ge 2\cdot
\md{0}/8$. Define $e_2=\cub{u\mbox{connects to a new node in }
  \nei{0}{2}{u} \mbox{ through an out-path in } P_1}$, and $X_2$ to be
the number of rounds for $e_2$ to occur. During time $X_1\le t\le
X_2$, $\prob{e_2}$ is at least $2\cdot\frac{1}{9n}$.
}

\junk{
Define
$e_2=\cub{u\mbox{connects to a new node in } \nei{0}{2}{u} \mbox{
    through an out-path in } P_1}$, and $X_2$ to be the number of
rounds for $e_2$ to occur. During time $X_1\le t\le X_2$, $\prob{e_2}$
is at least $2\cdot\frac{1}{9n}$.



Similarly, we define
$e_3,X_3,\dots,e_{\md{0}/8},X_{\md{0}/8}$ and derive $\prob{e_i} \ge
i/(9n)$.}

Let $T$ equal the random variable $X_1+X_2+\dots+X_{\md{0}/8}$, so
that $\dg{T}{u}\ge (1+1/8)\md{0}$.  By Lemma
\ref{lem:couponcorollary-10p}, $T$ is at most $(2+1)9n\ln n = 27n\ln
n$, with probability at least $1-1/n^2$, completing the proof of this
lemma.
\end{proof}

\begin{theorem}[{\bf Upper bound for two-hop walk process}]
\label{thm:graph+randwalk-10p}
For connected undirected graphs, the two-hop walk process completes in
$O(n\log^2 n)$ rounds with high probability.
\end{theorem}
\begin{proof}
We first show that in time $T=O(n\log n)$ time, the minimum degree of
the graph increases by a factor of $1/8$, i.e., $\md{T} \ge
\min\cub{(1+1/8)\md{0}, n-1}$. Then we can apply this argument $O(\log n)$
times, and thus, complete the proof of this theorem.

For each $u$ where $\dg{0}{u} < \min\cub{(1+1/8)\md{0}, n-1}$, we
analyze by the following 2 cases. First, if $|\nei{0}{2}{u}| \ge \md{0}/2$, by Lemma
\ref{lem:mingrowth-2-10p} we know as long as $|\nei{t}{2}{u}|\ge \md{0}/4$
for all $t\ge 0$, $\dg{T}{u} \ge\min\cub{(1+1/8)\md{0},n-1}$ with
probability $1-1/n^2$ where $T=O(n\log n)$. Whenever the condition is
not satisfied, we know at least $\md{0}/4$ nodes in $\nei{0}{2}{u}$
have been moved to $\nei{T}{1}{u}$, which means $\dg{T}{u}
\ge\min\cub{(1+1/4)\md{0},n-1}$.

Second, if $|\nei{0}{2}{u}| < \md{0}/2$, by Lemma
\ref{lem:mingrowth-1-10p} we know as long as $|\nei{t}{2}{u}| < \md{0}/2$
for all $t\ge 0$, $\dg{T}{u} \ge\min\cub{(1+1/8)\md{0},n-1}$ with
probability $1-1/n^2$ where $T=O(n\log n)$. Whenever the condition is
not satisfied, we are back to the analysis in the first case, and the
minimum degree will become $\min\cub{(1+1/8)\md{0},n-1}$ with
probability $1-1/n^2$.

Combining the the above two cases we get that with
probability $1-1/n$ the minimum degree of $G$
will become at least $\min\cub{(1+1/8)\md{0},n-1}$ in $O(n\log n)$ rounds,
since there are at most $n$ nodes whose degree is between
$\md{0}$ and $\min\cub{(1+1/8)\md{0},n-1}$,

Now we can apply the above argument $O(\log n)$ times, and have shown
the two-hop walk process completes in $O(n\log^2 n)$ with high
probability. 
\end{proof}

The proof of Theorem~\ref{thm:hop+lower-10p} is essentially the same as
that for Theorem \ref{thm:tri+lower-10p}, and is omitted.

\begin{theorem}[{\bf Lower bound for two-hop walk process}]
\label{thm:hop+lower-10p}
For any connected undirected graph $G$ that has $k \ge 1$ edges less
than the complete graph the two-hop process takes $\Omega(n \log
k)$ steps to complete with probability at least $1 - O\rb{e^{-k^{1/4}}}$.
\end{theorem}
